{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0cd4ad6d",
   "metadata": {},
   "source": [
    "# 1.乘最多的水\n",
    "\n",
    "给定一个长度为 `n` 的整数数组 `height` 。有 `n` 条垂线，第 `i` 条线的两个端点是 `(i, 0)` 和 `(i, height[i])` 。\n",
    "\n",
    "找出其中的两条线，使得它们与 `x` 轴共同构成的容器可以容纳最多的水。\n",
    "\n",
    "返回容器可以储存的最大水量。\n",
    "\n",
    "![img](https://zyc-learning-1309954661.cos.ap-nanjing.myqcloud.com/machine-learning-pic/09-53-22-9daebb6ebbdb925763fbd31e9a7aa329-question_11-c084c3.jpeg)\n",
    "\n",
    "> 输入：[1,8,6,2,5,4,8,3,7]\n",
    "> 输出：49 \n",
    "> 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。\n",
    "\n",
    "分别从左和右向中间夹逼，哪根线短移动哪根，因为想要探索更大的面积，必须试一试短的能不能更长，否则由于木桶原理，无论长的有多长，实际容纳水的面积是由短的决定的。每次移动都要比较和最大面积的大小关系。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "beeda749",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "49\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxArea(self, height: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(height) - 1\n",
    "        maxArea = -1\n",
    "        while left < right:\n",
    "            area = (right - left) * min(height[left], height[right])\n",
    "            maxArea = max(maxArea, area)\n",
    "            if height[left] > height[right]:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "        return maxArea\n",
    "\n",
    "\n",
    "sol = Solution()\n",
    "res = sol.maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])\n",
    "print(res)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1e2e2be",
   "metadata": {},
   "source": [
    "# 2.接雨水\n",
    "\n",
    "给定 `n` 个非负整数表示每个宽度为 `1` 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。\n",
    "\n",
    "**示例 1：**\n",
    "\n",
    "![rainwatertrap](https://zyc-learning-1309954661.cos.ap-nanjing.myqcloud.com/machine-learning-pic/10-15-52-a0b5725179e8d2e8540134afe72860be-rainwatertrap-4b80c6.png)\n",
    "\n",
    "> 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]\n",
    "> 输出：6\n",
    "> 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 \n",
    "\n",
    "![image-20250909103435870](https://zyc-learning-1309954661.cos.ap-nanjing.myqcloud.com/machine-learning-pic/10-34-35-dab3ddc3bdcad3bfc4b1565fa1651e35-image-20250909103435870-37a1b6.png)\n",
    "\n",
    "把每个格子都看成一个木桶，现在问题就简化为：求每个格子所成的木桶的左右两块木板的高度。这里的左/右木板指的是装多少水不会使其从左/右边流出来。\n",
    "\n",
    "求左木板的高度，使用最大前缀，就是从左到右看到当前这个格子的最大高度。\n",
    "\n",
    "求右木板的高度，使用最大后缀，就是从右到左看到当前这个格子的最大高度。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "dedb123c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def trap(self, height: List[int]) -> int:\n",
    "        left = []\n",
    "        right = []\n",
    "        res = []\n",
    "        n = len(height)\n",
    "        # 生成前缀\n",
    "        max_left = 0\n",
    "        k = 0\n",
    "        while k < n:\n",
    "            max_left = max(max_left, height[k])\n",
    "            left.append(max_left)\n",
    "            k += 1\n",
    "        # 生成后缀\n",
    "        max_right = 0\n",
    "        k = n-1\n",
    "        while k >= 0:\n",
    "            max_right = max(max_right, height[k])\n",
    "            right.insert(0, max_right)\n",
    "            k -= 1\n",
    "        # 计算水量\n",
    "        for k, h_k in enumerate(height):\n",
    "            min_height = min(left[k], right[k])\n",
    "            if min_height <= h_k:\n",
    "                res.append(0)\n",
    "            else:\n",
    "                res.append(min_height-h_k)\n",
    "        return sum(res)\n",
    "\n",
    "\n",
    "sol = Solution()\n",
    "res = sol.trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])\n",
    "print(res)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "tmp",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.23"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
